package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
	"time"
)

type qq struct {
	qqNum  int
	qqPass string
}

func mainb() {
	arr := []int{1, 9, 2, 8, 3, 7, 6, 4, 5, 10}

	lastarr := make(chan int) //管道
	go QuickSortThread(arr, lastarr, 1, 10)

	for v := range lastarr {
		fmt.Println(v)
	}
}

//    arr需要排序的数组，lastarr排序排列号，level级别，threads线程数量
func QuickSortThread(arr []int, lastarr chan int, level int, threads int) {
	level = level * 2 //每加深一个级，多一个线程
	if len(arr) == 0 {
		close(lastarr) //关闭管道
		return
	} else if len(arr) == 1 {
		lastarr <- arr[0] //为一个数据放入管道
		close(lastarr)    //关闭管道
		return
	} else {
		less := make([]int, 0)        //比我小的数据
		greater := make([]int, 0)     //比我大的数据
		midder := make([]int, 0)      //与我相等的数据
		left := arr[0]                //取得第一个数据
		midder = append(midder, left) //中间存放相等数据
		for i := 1; i < len(arr); i++ {
			if arr[i] < left {
				less = append(less, arr[i]) //处理小于的
			} else if arr[i] > left {
				greater = append(greater, arr[i]) //处理小于的
			} else {
				midder = append(midder, arr[i]) //处理等于
			}
		}
		left_ch := make(chan int, len(less))
		right_ch := make(chan int, len(greater)) //存放数组的管道
		if level <= threads {                    //如果线程超过执行数量，顺序调用，否则并发调用
			go QuickSortThread(less, left_ch, level, threads)
			go QuickSortThread(greater, right_ch, level, threads)
		} else {
			QuickSortThread(less, left_ch, level, threads)
			QuickSortThread(greater, right_ch, level, threads)
		}
		//数据压入管道
		for i := range left_ch {
			lastarr <- i
		}
		for _, v := range midder {
			lastarr <- v
		}
		for i := range right_ch {
			lastarr <- i
		}
		close(lastarr) //关闭管道

		return

	}
}

// 并发排序导致产生临时 变量  消耗内存
func main() {
	count := 84331445

	allstrs := make([]qq, count) //初始化数组
	path := "D:\\golang\\QQ.txt"
	qqfile, _ := os.Open(path) //打开文件
	defer qqfile.Close()       // 延迟关闭

	bf := bufio.NewReader(qqfile) // 读取数据
	i := 0

	for {
		line, _, err := bf.ReadLine() //读取一样文件

		if err == io.EOF { //读取到文件的最后一样
			break
		}

		linestr := string(line) //转化成字符串
		arrStr := strings.Split(linestr, "----")
		if len(arrStr) == 2 {
			allstrs[i].qqNum, _ = strconv.Atoi(arrStr[0])
			allstrs[i].qqPass = arrStr[1]
		}

		i++
	}
	fmt.Println("数据载入内存")
	time.Sleep(time.Second * 1)

	fmt.Println("开始排序 数据长度：", len(allstrs))

	t1 := time.Now()
	lastarr := make(chan qq) //管道
	QuickSortQQ(allstrs, lastarr, 1, count)
	fmt.Println("执行排序的时间", time.Since(t1))
}

func QuickSortQQ(arr []qq, lastarr chan qq, level int, threads int) {
	level = level * 2 //每加深一个级，多一个线程
	if len(arr) == 0 {
		close(lastarr) //关闭管道
		return
	} else if len(arr) == 1 {
		lastarr <- arr[0] //为一个数据放入管道
		close(lastarr)    //关闭管道
		return
	} else {
		less := make([]qq, 0)         //比我小的数据
		greater := make([]qq, 0)      //比我大的数据
		midder := make([]qq, 0)       //与我相等的数据
		left := arr[0]                //取得第一个数据
		midder = append(midder, left) //中间存放相等数据
		for i := 1; i < len(arr); i++ {
			if arr[i].qqNum < left.qqNum {
				less = append(less, arr[i]) //处理小于的
			} else if arr[i].qqNum > left.qqNum {
				greater = append(greater, arr[i]) //处理小于的
			} else {
				midder = append(midder, arr[i]) //处理等于
			}
		}
		left_ch := make(chan qq, len(less))
		right_ch := make(chan qq, len(greater)) //存放数组的管道
		if level <= threads {                   //如果线程超过执行数量，顺序调用，否则并发调用
			go QuickSortQQ(less, left_ch, level, threads)
			go QuickSortQQ(greater, right_ch, level, threads)
		} else {
			QuickSortQQ(less, left_ch, level, threads)
			QuickSortQQ(greater, right_ch, level, threads)
		}
		//数据压入管道
		for i := range left_ch {
			lastarr <- i
		}
		for _, v := range midder {
			lastarr <- v
		}
		for i := range right_ch {
			lastarr <- i
		}
		close(lastarr) //关闭管道

		return

	}
}
